package visualizer.client.bst;

/**
 * User: DDovzhenko
 * Date: 28.12.13
 * Time: 23:09
 */
public class BinaryTree {
    BNode rootNode;

    public BinaryTree() {
        rootNode = null;
    }

    protected BNode insertAB(BNode rootNode, BNode newNode) {
        if (rootNode == null) {
            rootNode = newNode;
        } else if (newNode.getValue().compareTo(rootNode.getValue()) == 0) {
            return rootNode;
        } else if (newNode.getValue().compareTo(rootNode.getValue()) < 0) {
            rootNode.setLeftBNode(insertAB(rootNode.getLeftBNode(), newNode));
        } else {
            rootNode.setRightBNode(insertAB(rootNode.getRightBNode(), newNode));
        }
        updateSize(rootNode);
        return rootNode;
    }

    public void insertBST(Integer value) {
        BNode anyClassBTNode = new BNode(value);
        rootNode = insertAB(rootNode, anyClassBTNode);
    }

    public int getMaxDepth() {
        return maxDepth(rootNode);
    }

    public BNode getRoot() {
        return rootNode;
    }

    public void setRootNode(BNode rootNode) {
        this.rootNode = rootNode;
    }

    public BinaryTree copyTree(boolean deepCopy) {
        BinaryTree tree = new BinaryTree();
        tree.setRootNode(copyBST(this.rootNode, deepCopy));
        return tree;
    }

    private BNode copyBST(BNode rootNode, boolean deepCopy) {
        if (rootNode == null) {
            return null;
        }

        BNode node = new BNode(rootNode.getValue());
        node.setSize(rootNode.getSize());
        if (deepCopy) {
            node.setInnerColor(rootNode.getInnerColor());
            node.setOuterColor(rootNode.getOuterColor());
            node.setVisible(rootNode.isVisible());
        }
        node.setLeftBNode(copyBST(rootNode.getLeftBNode(), deepCopy));
        node.setRightBNode(copyBST(rootNode.getRightBNode(), deepCopy));

        return node;
    }

    public void updateSize(BNode v) {
        if (v != null) v.setSize(size(v.getLeftBNode()) + size(v.getRightBNode()) + 1);
    }

    public int size(BNode v) {
        return (v != null) ? v.getSize() : 0;
    }

    public void refreshSizes() {
        refreshSizes(rootNode);
    }

    private int refreshSizes(BNode node) {
        if (node == null) return 0;
        int leftSize = refreshSizes(node.getLeftBNode());
        int rightSize = refreshSizes(node.getRightBNode());
        int curSize = leftSize + rightSize + 1;
        node.setSize(curSize);
        return curSize;
    }

    public void refreshParents() {
        refreshParents(rootNode, null);
    }

    private void refreshParents(BNode node, BNode parent) {
        if (node == null) {
            return;
        }
        node.setParent(parent);
        refreshParents(node.getLeftBNode(), node);
        refreshParents(node.getRightBNode(), node);
    }

    public static int maxDepth(BNode node) {
        if (node == null) return 0;
        int leftHeight = maxDepth(node.getLeftBNode());
        int rightHeight = maxDepth(node.getRightBNode());
        return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
    }
}